package org.genesilico.workflow2.graphs.tests;

import org.genesilico.workflow2.graphs.GraphNode;
import org.genesilico.workflow2.graphs.GraphUtilities;
import org.genesilico.workflow2.graphs.Node;
import org.genesilico.workflow2.graphs.GraphUtilities.GraphError;
import org.genesilico.workflow2.graphs.isomorphism.Graph;
import org.junit.Assert;
import org.junit.Test;

public class SimpleTest {

	@Test(expected = IllegalArgumentException.class)
	public void test1() {
		new Graph(null);
	}

	/**
	 * Tests comparing nodes.
	 */
	@Test
	public void test2() {
		GraphNode[] gN1 = new GraphNode[3];
		GraphNode[] gN2 = new GraphNode[3];
		for (int i = 0; i < 3; i++) {
			gN1[i] = new GraphNode(i, new Node(""), new int[0], new int[0]);
			gN2[i] = new GraphNode(i, new Node(""), new int[0], new int[0]);
		}
		gN1[0].content.content = "a";
		gN1[1].content.content = "a";
		gN1[2].content.content = "b";

		gN2[0].content.content = "a";
		gN2[1].content.content = "b";
		gN2[2].content.content = "b";

		Assert.assertTrue(!GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN2));
	}

	/**
	 * Checks isomorphism checking for empty graph and for graph with only one
	 * node.
	 */
	@Test
	public void emptyGraphsTest() {
		Assert
				.assertTrue(GraphUtilities.hasError(null, true, true, true) == GraphError.Good);
		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(null,
				null));
		GraphNode[] gN = new GraphNode[0];
		Assert
				.assertTrue(GraphUtilities.hasError(gN, true, true, true) == GraphError.Good);
		Assert
				.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN,
						gN));
		Assert.assertTrue(!GraphUtilities.assessIsomorphismBetweenGraphs(null,
				gN));
		
		gN = new GraphNode[1];
		gN[0] = new GraphNode(0, new Node("test"), null, null);
		Assert
				.assertTrue(GraphUtilities.hasError(gN, true, true, true) == GraphError.Good);
		Assert
				.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN,
						gN));
		gN[0].content = new Node("asd");
		gN[0].children = new int[0];
		gN[0].parents = new int[0];
		Assert
				.assertTrue(GraphUtilities.hasError(gN, true, true, true) == GraphError.Good);
		Assert
				.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN,
						gN));
	}

	@Test
	public void isomorphismTest1() {
		GraphNode[] gN1 = new GraphNode[10];
		GraphNode[] gN2 = new GraphNode[10];

		for (int i = 0; i < 10; i++) {
			gN1[i] = new GraphNode(i, null, null, null);
			gN2[i] = new GraphNode(i, null, null, null);
			gN1[i].content = new Node("asda");
			gN2[i].content = new Node("asda");
			gN1[i].children = null;// new int[0];
			gN1[i].parents = null;// new int[0];
			gN2[i].children = null;// new int[0];
			gN2[i].parents = null;// new int[0];
		}
		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN1));
		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN2));

		gN1[0].content.content = "as";
		Assert.assertTrue(!GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN2));
		gN1[0].content.content = "asda";
		gN1[0].children = new int[2];
		gN1[0].children[0] = 1;
		gN1[0].children[1] = 3;

		gN1[1].parents = new int[1];
		gN1[1].parents[0] = 0;
		gN1[1].children = new int[3];
		gN1[1].children[0] = 2;
		gN1[1].children[1] = 4;
		gN1[1].children[2] = 3;

		gN1[2].parents = new int[1];
		gN1[2].parents[0] = 1;

		gN1[3].parents = new int[2];
		gN1[3].parents[0] = 1;
		gN1[3].parents[1] = 0;
		gN1[3].children = new int[1];
		gN1[3].children[0] = 5;

		gN1[4].parents = new int[1];
		gN1[4].parents[0] = 1;
		gN1[4].children = new int[1];
		gN1[4].children[0] = 6;

		gN1[5].parents = new int[1];
		gN1[5].parents[0] = 3;
		gN1[5].children = new int[1];
		gN1[5].children[0] = 6;

		gN1[6].parents = new int[2];
		gN1[6].parents[0] = 5;
		gN1[6].parents[1] = 4;
		gN1[6].children = new int[2];
		gN1[6].children[0] = 7;
		gN1[6].children[1] = 8;

		gN1[7].parents = new int[1];
		gN1[7].parents[0] = 6;

		gN1[8].parents = new int[1];
		gN1[8].parents[0] = 6;
		gN1[8].children = new int[1];
		gN1[8].children[0] = 9;

		gN1[9].parents = new int[1];
		gN1[9].parents[0] = 8;

		Assert
				.assertTrue(GraphUtilities.hasError(gN1, true, true, true) == GraphError.Good);
		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN1));

		gN2[0].parents = new int[1];
		gN2[0].parents[0] = 8;
		gN2[0].children = new int[1];
		gN2[0].children[0] = 9;

		gN2[1].parents = new int[1];
		gN2[1].parents[0] = 9;
		gN2[1].children = new int[1];
		gN2[1].children[0] = 5;

		gN2[2].parents = new int[1];
		gN2[2].parents[0] = 7;
		gN2[2].children = new int[3];
		gN2[2].children[0] = 3;
		gN2[2].children[1] = 4;
		gN2[2].children[2] = 8;

		gN2[3].parents = new int[1];
		gN2[3].parents[0] = 2;

		gN2[4].parents = new int[1];
		gN2[4].parents[0] = 2;
		gN2[4].children = new int[1];
		gN2[4].children[0] = 9;

		gN2[5].parents = new int[1];
		gN2[5].parents[0] = 1;

		gN2[6].parents = new int[1];
		gN2[6].parents[0] = 9;

		gN2[7].children = new int[2];
		gN2[7].children[0] = 2;
		gN2[7].children[1] = 8;

		gN2[8].parents = new int[2];
		gN2[8].parents[0] = 7;
		gN2[8].parents[1] = 2;
		gN2[8].children = new int[1];
		gN2[8].children[0] = 0;

		gN2[9].parents = new int[2];
		gN2[9].parents[0] = 4;
		gN2[9].parents[1] = 0;
		gN2[9].children = new int[2];
		gN2[9].children[0] = 6;
		gN2[9].children[1] = 1;

		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN2,
				gN2));
		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN2));

		gN1[6].parents = new int[1];
		gN1[6].parents[0] = 4;
		gN1[5].children[0] = 1;
		gN1[1].parents = new int[2];
		gN1[1].parents[0] = 0;
		gN1[1].parents[1] = 5;

		Assert
				.assertTrue(GraphUtilities.hasError(gN1, true, true, true) == GraphError.HasCycle);
		Assert.assertTrue(!GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN2));
	}

	/**
	 * Tests algorithm's efficiency for a typical graph - 10 nodes, small number
	 * of edges.
	 */
	@Test
	public void efficiencyTest1() {
		GraphNode[] gN1 = new GraphNode[10];
		GraphNode[] gN2 = new GraphNode[10];

		for (int i = 0; i < 10; i++) {
			gN1[i] = new GraphNode(i, null, null, null);
			gN2[i] = new GraphNode(i, null, null, null);
			gN1[i].content = new Node("asda");
			gN2[i].content = new Node("asda");
			gN1[i].children = null;// new int[0];
			gN1[i].parents = null;// new int[0];
			gN2[i].children = null;// new int[0];
			gN2[i].parents = null;// new int[0];
		}

		gN1[0].children = new int[2];
		gN1[0].children[0] = 1;
		gN1[0].children[1] = 3;

		gN1[1].parents = new int[1];
		gN1[1].parents[0] = 0;
		gN1[1].children = new int[3];
		gN1[1].children[0] = 2;
		gN1[1].children[1] = 4;
		gN1[1].children[2] = 3;

		gN1[2].parents = new int[1];
		gN1[2].parents[0] = 1;

		gN1[3].parents = new int[2];
		gN1[3].parents[0] = 1;
		gN1[3].parents[1] = 0;
		gN1[3].children = new int[1];
		gN1[3].children[0] = 5;

		gN1[4].parents = new int[1];
		gN1[4].parents[0] = 1;
		gN1[4].children = new int[1];
		gN1[4].children[0] = 6;

		gN1[5].parents = new int[1];
		gN1[5].parents[0] = 3;
		gN1[5].children = new int[1];
		gN1[5].children[0] = 6;

		gN1[6].parents = new int[2];
		gN1[6].parents[0] = 5;
		gN1[6].parents[1] = 4;
		gN1[6].children = new int[2];
		gN1[6].children[0] = 7;
		gN1[6].children[1] = 8;

		gN1[7].parents = new int[1];
		gN1[7].parents[0] = 6;

		gN1[8].parents = new int[1];
		gN1[8].parents[0] = 6;
		gN1[8].children = new int[1];
		gN1[8].children[0] = 9;

		gN1[9].parents = new int[1];
		gN1[9].parents[0] = 8;

		gN2[0].parents = new int[1];
		gN2[0].parents[0] = 8;
		gN2[0].children = new int[1];
		gN2[0].children[0] = 9;

		gN2[1].parents = new int[1];
		gN2[1].parents[0] = 9;
		gN2[1].children = new int[1];
		gN2[1].children[0] = 5;

		gN2[2].parents = new int[1];
		gN2[2].parents[0] = 7;
		gN2[2].children = new int[3];
		gN2[2].children[0] = 3;
		gN2[2].children[1] = 4;
		gN2[2].children[2] = 8;

		gN2[3].parents = new int[1];
		gN2[3].parents[0] = 2;

		gN2[4].parents = new int[1];
		gN2[4].parents[0] = 2;
		gN2[4].children = new int[1];
		gN2[4].children[0] = 9;

		gN2[5].parents = new int[1];
		gN2[5].parents[0] = 1;

		gN2[6].parents = new int[1];
		gN2[6].parents[0] = 9;

		gN2[7].children = new int[2];
		gN2[7].children[0] = 2;
		gN2[7].children[1] = 8;

		gN2[8].parents = new int[2];
		gN2[8].parents[0] = 7;
		gN2[8].parents[1] = 2;
		gN2[8].children = new int[1];
		gN2[8].children[0] = 0;

		gN2[9].parents = new int[2];
		gN2[9].parents[0] = 4;
		gN2[9].parents[1] = 0;
		gN2[9].children = new int[2];
		gN2[9].children[0] = 6;
		gN2[9].children[1] = 1;

		// GraphUtilities.log.

		for (int i = 0; i < 100000; i++)
			GraphUtilities.assessIsomorphismBetweenGraphs(gN1, gN2);
		
		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN2));
	}

	/**
	 * Tests
	 * {@link GraphUtilities#hasError(GraphNode[], boolean, boolean, boolean)}
	 * function.
	 */
	@Test
	public void cycleTest1() {
		GraphNode[] gN1 = new GraphNode[10];
		for (int i = 0; i < gN1.length; i++) {
			gN1[i] = new GraphNode(i, null, null, null);
			// gN1[i].content = null;
			gN1[i].parents = null;
			gN1[i].children = null;
		}
		Assert
				.assertTrue(GraphUtilities.hasError(gN1, true, true, true) == GraphError.Good);

		gN1[0].children = new int[1];
		gN1[0].parents = new int[1];
		gN1[1].children = new int[1];
		gN1[1].parents = new int[1];
		gN1[0].children[0] = 1;
		gN1[0].parents[0] = 1;
		gN1[1].children[0] = 0;
		gN1[1].parents[0] = 0;

		Assert
				.assertTrue(GraphUtilities.hasError(gN1, true, true, true) == GraphError.HasCycle);

		gN1[0].children = new int[1];
		gN1[0].parents = new int[0];
		gN1[1].children = new int[1];
		gN1[1].parents = new int[2];
		gN1[2].children = new int[1];
		gN1[2].parents = new int[1];

		gN1[0].children[0] = 1;
		gN1[1].children[0] = 2;
		gN1[1].parents[0] = 0;
		gN1[1].parents[1] = 2;
		gN1[2].children[0] = 1;
		gN1[2].parents[0] = 1;

		Assert
				.assertTrue(GraphUtilities.hasError(gN1, true, true, true) == GraphError.HasCycle);

		gN1[0].children = new int[1];
		gN1[0].parents = new int[0];
		gN1[1].children = new int[2];
		gN1[1].parents = new int[1];
		gN1[2].children = new int[0];
		gN1[2].parents = new int[1];
		gN1[3].children = new int[0];
		gN1[3].parents = new int[1];

		gN1[0].children[0] = 1;
		gN1[1].children[0] = 2;
		gN1[1].children[1] = 3;
		gN1[1].parents[0] = 0;
		gN1[2].parents[0] = 1;
		gN1[3].parents[0] = 1;

		Assert
				.assertTrue(GraphUtilities.hasError(gN1, true, true, true) == GraphError.Good);

	}

	@Test
	public void allPermutations() {
		GraphNode[] gN1 = new GraphNode[4];
		GraphNode[] gN2 = new GraphNode[4];
		for (int i = 0; i < 4; i++) {
			gN1[i] = new GraphNode(i, new Node("sd"), null, null);
			gN2[i] = new GraphNode(i, new Node("sd"), null, null);
			gN1[i].children = null;// new int[0];
			gN1[i].parents = null;// new int[0];
			gN2[i].children = null;// new int[0];
			gN2[i].parents = null;// new int[0];
		}
		gN1[0].children = new int[2];
		gN1[0].children[0] = 2;
		gN1[0].children[1] = 3;

		gN1[1].children = new int[2];
		gN1[1].children[0] = 2;
		gN1[1].children[1] = 3;

		gN1[2].parents = new int[2];
		gN1[2].parents[0] = 0;
		gN1[2].parents[1] = 1;

		gN1[3].parents = new int[2];
		gN1[3].parents[0] = 0;
		gN1[3].parents[1] = 1;

		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN1));

		gN2[0].children = new int[2];
		gN2[0].children[0] = 2;
		gN2[0].children[1] = 2;

		gN2[1].children = new int[2];
		gN2[1].children[0] = 3;
		gN2[1].children[1] = 3;

		gN2[2].parents = new int[2];
		gN2[2].parents[0] = 0;
		gN2[2].parents[1] = 0;

		gN2[3].parents = new int[2];
		gN2[3].parents[0] = 1;
		gN2[3].parents[1] = 1;
		Assert.assertTrue(GraphUtilities.hasError(gN2, true, true, true).equals(GraphError.HasMultipleEdges));
		Assert.assertTrue(GraphUtilities.hasError(gN2, false, true, true).equals(GraphError.HasMultipleEdges));
		Assert.assertTrue(GraphUtilities.hasError(gN2, true, false, true).equals(GraphError.Good));
		Assert.assertTrue(GraphUtilities.hasError(gN2, false, false, true).equals(GraphError.Good));
		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN2, gN2));
		Assert.assertFalse(GraphUtilities.assessIsomorphismBetweenGraphs(gN1, gN2));
		
		gN1 = new GraphNode[10];
		gN2 = new GraphNode[10];
		for (int i = 0; i < 10; i++) {
			gN1[i] = new GraphNode(i, new Node("sd"), null, null);
			gN2[i] = new GraphNode(i, new Node("sd"), null, null);
		}
		for(int i = 0; i < 5; i++)
		{
			gN1[i].children = new int[3];
			gN1[i].parents = new int[0];
			gN2[i].children = new int[3];
			gN2[i].parents = new int[0];
			gN1[i + 5].children = new int[0];
			gN2[i + 5].children = new int[0];
		}
		
		gN1[0].children[0] = 5;
		gN1[0].children[1] = 6;
		gN1[0].children[2] = 7;
		
		gN1[1].children[0] = 5;
		gN1[1].children[1] = 6;
		gN1[1].children[2] = 7;
		
		gN1[2].children[0] = 6;
		gN1[2].children[1] = 7;
		gN1[2].children[2] = 8;
		
		gN1[3].children[0] = 7;
		gN1[3].children[1] = 8;
		gN1[3].children[2] = 9;
		
		gN1[4].children[0] = 7;
		gN1[4].children[1] = 8;
		gN1[4].children[2] = 9;
		
		gN2[0].children[0] = 5;
		gN2[0].children[1] = 8;
		gN2[0].children[2] = 7;
		
		gN2[1].children[0] = 5;
		gN2[1].children[1] = 6;
		gN2[1].children[2] = 7;
		
		gN2[2].children[0] = 6;
		gN2[2].children[1] = 7;
		gN2[2].children[2] = 8;
		
		gN2[3].children[0] = 7;
		gN2[3].children[1] = 8;
		gN2[3].children[2] = 9;
		
		gN2[4].children[0] = 7;
		gN2[4].children[1] = 6;
		gN2[4].children[2] = 9;		
		
		gN1[5].parents = new int[2];
		gN1[5].parents[0] = 0;
		gN1[5].parents[1] = 1;				
		
		gN1[6].parents = new int[3];
		gN1[6].parents[0] = 0;
		gN1[6].parents[1] = 1;
		gN1[6].parents[2] = 2;
		
		gN1[7].parents = new int[5];
		gN1[7].parents[0] = 0;
		gN1[7].parents[1] = 1;
		gN1[7].parents[2] = 2;
		gN1[7].parents[3] = 3;
		gN1[7].parents[4] = 4;
		
		gN1[8].parents = new int[3];
		gN1[8].parents[0] = 2;
		gN1[8].parents[1] = 3;
		gN1[8].parents[2] = 4;
		
		gN1[9].parents = new int[2];		
		gN1[9].parents[0] = 3;
		gN1[9].parents[1] = 4;
		
		gN2[5].parents = new int[2];
		gN2[5].parents[0] = 0;
		gN2[5].parents[1] = 1;				
		
		gN2[6].parents = new int[3];
		gN2[6].parents[0] = 4;
		gN2[6].parents[1] = 1;
		gN2[6].parents[2] = 2;
		
		gN2[7].parents = new int[5];
		gN2[7].parents[0] = 0;
		gN2[7].parents[1] = 1;
		gN2[7].parents[2] = 2;
		gN2[7].parents[3] = 3;
		gN2[7].parents[4] = 4;
		
		gN2[8].parents = new int[3];
		gN2[8].parents[0] = 2;
		gN2[8].parents[1] = 3;
		gN2[8].parents[2] = 0;
		
		gN2[9].parents = new int[2];		
		gN2[9].parents[0] = 3;
		gN2[9].parents[1] = 4;
		
		Assert.assertTrue(GraphUtilities.hasError(gN1, true, false, true).equals(GraphError.Good));
		Assert.assertTrue(GraphUtilities.hasError(gN2, true, false, true).equals(GraphError.Good));
		Assert.assertFalse(GraphUtilities.assessIsomorphismBetweenGraphs(gN1, gN2));
		
	}

	/**
	 * Tests a graph that was specifically designed to heavily use
	 * {@link Graph#findClearFromClear(Graph)} function.
	 */
	@Test
	public void findClearFromClear() {
		GraphNode[] gN1 = new GraphNode[10];
		GraphNode[] gN2 = new GraphNode[10];
		for (int i = 0; i < 10; i++) {
			gN1[i] = new GraphNode(i, new Node("sd"), null, null);
			gN2[i] = new GraphNode(i, new Node("sd"), null, null);
			gN1[i].children = new int[1];
			gN1[i].parents = new int[1];
			gN2[i].children = new int[1];
			gN2[i].parents = new int[1];
		}

		for (int i = 0; i < 10; i++) {
			gN1[i].children[0] = i + 2;
			gN1[i].parents[0] = i - 2;
		}
		gN1[0].parents = new int[0];
		gN1[1].parents = new int[0];
		gN1[8].children = new int[0];
		gN1[9].children = new int[0];

		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN1));

		gN1[9].content.content = "a";
		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN1));
	}

	@Test
	public void efficiencyTest2() {
		int size = 100;
		GraphNode[] gN1 = new GraphNode[size];
		GraphNode[] gN2 = new GraphNode[size];
		for (int i = 0; i < size; i++) {
			gN1[i] = new GraphNode(i, new Node("sd"), null, null);
			gN2[i] = new GraphNode(i, new Node("sd"), null, null);
			gN1[i].children = new int[1];
			gN1[i].parents = new int[1];
			gN2[i].children = new int[1];
			gN2[i].parents = new int[1];
		}

		for (int i = 0; i < size; i++) {
			gN1[i].children[0] = i + 2;
			gN1[i].parents[0] = i - 2;
			gN2[i].children[0] = i + 2;
			gN2[i].parents[0] = i - 2;
		}
		gN1[0].parents = new int[0];
		gN1[1].parents = new int[0];
		gN1[size - 2].children = new int[0];
		gN1[size - 1].children = new int[0];
		gN2[0].parents = new int[0];
		gN2[1].parents = new int[0];
		gN2[size - 2].children = new int[0];
		gN2[size - 1].children = new int[0];

		for (int i = 0; i < 10000; i++) {
			gN1[0].content.content = "sd";
			GraphUtilities.assessIsomorphismBetweenGraphs(gN1, gN2);
			gN1[0].content.content = "a";
			GraphUtilities.assessIsomorphismBetweenGraphs(gN1, gN2);
		}
		gN1[0].content.content = "sd";
		Assert.assertTrue(GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN2));
		gN1[0].content.content = "a";
		Assert.assertFalse(GraphUtilities.assessIsomorphismBetweenGraphs(gN1,
				gN2));
	}
}
